#include <stdio.h>
#include <string.h>

#define BUFFER_SIZE 10

static int swapNum(int *val1, int *val2)
{
    int tmpVal = *val1;
    *val1 = *val2;
    *val2 = tmpVal;
    return 0;
}

static int searchInsertPos(int* nums, int numsSize, int target) 
{
    int left = 0;
    int right = numsSize - 1;
    int mid = 0;//用于存储中间值位置的下标
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (nums[mid] <= target)
            left = mid + 1;
        else 
            right = mid - 1;
    }
    return left;// 返回起始位置left，即为插入位置
}

/* 插入排序 */
/* 默认第一个元素已经排好序 */
int insertSort(int *nums, int numSize)
{
    int insertPos = 0;
    /* 插入排序 */
    /* 默认第一个元素已经排好序 */
    for (int idx = 1; idx < numSize; idx++)
    {
        int copyNum = nums[idx];
        /* 索引备份 */
        int prevIdx = idx - 1;

        /* 要考虑临界值的情况 ：prevIdx < 0*/
        while (nums[prevIdx] > copyNum && (prevIdx >= 0))
        {
            /* 后移 */
            nums[prevIdx + 1] = nums[prevIdx];

            prevIdx--;
        }

        /* nums[prevIdx] <= copyNum || prevIdx < 0 */
        nums[prevIdx + 1] = copyNum;


        /* 插入排序优化 */

        /* 找到要排序元素要插入的位置 O(logN) */
        insertPos = searchInsertPos(nums, idx, copyNum);

#if 0
        while (nums[prevIdx] > copyNum && prevIdx >= 0)
        {
            nums[prevIdx + 1] = nums[prevIdx];
            prevIdx--;
        }
        // nums[prevIdx] <= copyNum && prevIdx = -1
        nums[prevIdx + 1] = copyNum;
        #else
        /* 数组迁移, 从后向前迁移. */
        for (int jdx = idx; jdx > insertPos; jdx--)
        {
            nums[jdx] = nums[jdx - 1];
        }
        nums[insertPos] = copyNum;
#endif 

    }
    return 0;
}

/* 打印 */
int printNums(int *nums, int numSize)
{
    for (int idx = 0; idx < numSize; idx++)
    {
        printf("%d\t", nums[idx]);
    }
    printf("\n");
}

int main()
{
    int nums[BUFFER_SIZE] = {7, 21, 12, 5, 32, 45, 17, 87, 22, 9}; 

    insertSort(nums, BUFFER_SIZE);
    printNums(nums, BUFFER_SIZE);

    return 0;
}